/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package kuhnmunkresproject;

import java.util.LinkedList;

/**
 *
 * @author Agustin
 */
public class Paso2 {
    
    private LinkedList<Integer> S, T, Ns;
    
    public Paso2(){
        this.S = new LinkedList<Integer>();
        this.T = new LinkedList<Integer>();
        this.Ns = new LinkedList<Integer>();
    }
    
    public void Iniciar(Matriz m, int noSaturadoInicial, int [][] Mpesos)
    {
        int y = 0, z = 0, k = 0;
        
        // Agregar "u" a "S"
        this.S.add(noSaturadoInicial);
        // Generar los vecinos de "S"
        this.AgregarVecinos(m);
        
        // Sacar el primer vecino de S y comparar con T
        // Si no son iguales
        while(!this.CompararVecinosConT(m)){
            y = this.Pop();
            z = m.VecinosMaching(y);
            
            if(z == -1)
            {
                z = m.NoSaturados()[k];
                k++;
            }
            
            this.T.add(y);
            this.S.add(z);
        }
        
        // Llamamos al paso 3
        LinkedList<Integer> Tnegada = new LinkedList<Integer>();
        int min = 0, ult = (Mpesos.length - 1), aux = Integer.MAX_VALUE;
        for(int i = 0; i < Mpesos.length -1; i++)
        {
                 if(!T.contains(i+1)){
                     Tnegada.add(i+1);
                }    
        }
        for(int i = 0; i < S.size(); i++)
        {
             for(int j = 0; j < Tnegada.size(); j++){
                 min = (Mpesos[S.get(i) - 1][ult] + Mpesos[ult][Tnegada.get(j) - 1] - Mpesos[S.get(i) - 1][Tnegada.get(j) - 1]);
                 if (min < aux && min != 0){
                    aux = min; 
                 }     
             }
        }
        // retiquetado de vertices
        for(int i = 0; i < S.size(); i++)
        {
            Mpesos[S.get(i)-1][ult] = (Mpesos[S.get(i)-1][ult] - aux);
        }
        for(int i = 0; i < T.size(); i++)
        {
            Mpesos[ult][T.get(i)-1] = (Mpesos[ult][T.get(i)-1] + aux);
        }

        m.GenerarGrafo(Mpesos);
        m.GenerarMatching(Mpesos);
        //////////////////
    }
    
    private void AgregarVecinos(Matriz m)
    {
        LinkedList<Integer> vecinos = new LinkedList<Integer>();
        
        for(int i = 0; i < this.S.size(); i++)
        {
            vecinos = m.VecinosAdyacencia(this.S.get(i));
            
            for(int j = 0; j < vecinos.size(); j++)
            {
                if(!this.Ns.contains(vecinos.get(j)))
                {
                    this.Ns.add(vecinos.get(j));
                }
            }
        }
    }
    
    private boolean CompararVecinosConT(Matriz m)
    {
        boolean ban = false;
        
        if(T.size() > 0)
        {
            if(T.size() == Ns.size())
            {
                ban = true;
            }
        }
        
        return ban;
    }
    
    private int Pop()
    {
        int ret = 0;
        
        for(int i = 0; i < this.Ns.size(); i++)
        {
            if(!this.T.contains(this.Ns.get(i)))
            {
                ret = this.Ns.get(i);
                break;
            }
        }  
        return ret;
    }
}
